﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace TowersOfHanoi
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();

            //TowersOfHanoi();
            SortStackUsingStack();
        }

        void SortStackUsingStack()
        {
            Stack<int> unsortedStack = new Stack<int>();
            Stack<int> sortedStack = new Stack<int>();

            //unsortedStack.Push(3);
            //unsortedStack.Push(8);
            //unsortedStack.Push(1);
            //unsortedStack.Push(15);
            //unsortedStack.Push(8);
            //unsortedStack.Push(7);

            Random random = new Random(35);
            for (int i = 0; i < 7000; i++)
            {
                unsortedStack.Push(random.Next(10000));
            }

            while (unsortedStack.Count > 0)
            {
                int temp = unsortedStack.Pop();
                while (sortedStack.Count > 0 &&
                    sortedStack.Peek() > temp)
                {
                    unsortedStack.Push(sortedStack.Pop());
                }
                sortedStack.Push(temp);
            }

            bool test = true;
        }

        int m_N = 10;
        Stack<int> m_source = new Stack<int>();
        Stack<int> m_aux = new Stack<int>();
        Stack<int> m_dest = new Stack<int>();

        void TowersOfHanoi()
        {
            for (int i = m_N; i > 0; i--)
            {
                m_source.Push(i);
            }

            Solve(m_N, m_source, m_aux, m_dest);

            this.Text = "Took " + string.Format("{0:0,0}", m_Moves) + " moves";
        }

        ulong m_Moves = 0;
        void Solve(int n, Stack<int> source, Stack<int> aux, Stack<int> dest)
        {
            if (n == 0)
                return;

            Solve(n - 1, source, dest, aux);
            dest.Push(source.Pop());
            m_Moves++;
            Solve(n - 1, aux, source, dest);
        }
    }
}
